package other.sort;

import common.util.MyUtil;

/**
 * 时间复杂度 O(nlogn)
 * 空间复杂度 O(n)
 *
 * @author guichang
 * @date 2020/9/24
 */

@SuppressWarnings("all")
public class P5_归并排序 {

    public static void main(String[] args) {
        int[] nums = MyUtil.createRandomArray(50, 1, 99);
        mergeSort(nums);
        MyUtil.printInt(nums);
    }

    public static void mergeSort(int[] array) {
        // 边界条件
        if (array == null || array.length < 2) {
            return;
        }
        // 递归过程
        mergeSortSub(array, 0, array.length - 1);

    }

    public static void mergeSortSub(int[] array, int left, int right) {
        // 递归终止条件
        if (left >= right) {
            return;
        }
        int mid = left + ((right - left) >> 1);
        mergeSortSub(array, left, mid);
        mergeSortSub(array, mid + 1, right);
        // 左右已排好序，合并一下
        merge(array, left, mid, right);
    }

    public static void merge(int[] array, int left, int mid, int right) {
        int[] help = new int[right - left + 1];
        int i = 0; // 辅助数组的当前位置
        int p1 = left; // 左边数组指针
        int p2 = mid + 1; // 右边数组指针
        // 都不越界的情况
        while (p1 <= mid && p2 <= right) {
            help[i++] = array[p1] <= array[p2] ? array[p1++] : array[p2++];
        }
        // 哪边不越界就把哪边的剩下的全部处理，以下仅会出现一种情况
        while (p1 <= mid) {
            help[i++] = array[p1++];
        }
        while (p2 <= right) {
            help[i++] = array[p2++];
        }
        // array的left到right范围值覆盖
        for (int j = 0; j < help.length; j++) {
            array[left + j] = help[j];
        }

    }


}